package com.javabasic.algorithm.leetcode;

/**
 * @author xiongmin
 * @version 0.0.1
 * @description Created by work on 2021/10/20 11:12 下午
 * @see
 */
public class MinimumMovesToEqualArrayElements {

    /**
     * n-1个数均加一，可以逆过来看就是又一个数减一，所以我们只要找到最小的数是哪个，然后以这个数为基准其他所有数到这个基准数的距离总和即为结果
     * @param nums
     * @return
     */
    public int minMoves(int[] nums) {
        int len = nums.length;
        quickSort(nums, 0, len - 1);
        int result = 0;
        int tagValue = nums[0];
        for (int i = 1; i < len; i++) {
            result += nums[i] - tagValue;
        }
        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();
        return result;
    }

    /**
     * 快速排序
     *
     * @param nums
     * @param left
     * @param right
     */
    private void quickSort(int[] nums, int left, int right) {
        if (left < right) {
            int tag = executeSort(nums, left, right);
            quickSort(nums, left, tag - 1);
            quickSort(nums, tag + 1, right);
        }
    }

    private int executeSort(int[] nums, int left, int right) {
        int tagValue = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= tagValue) right--;
            nums[left++] = nums[right];
            while (left < right && nums[left] < tagValue) left++;
            nums[right--] = nums[left];
        }
        nums[left] = tagValue;
        return left;
    }


    
}
